package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * leetcode 18. 四数之和
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/18 11:21
 */
public class E18 {
    /**
     * 四数之和
     * @param nums 数组
     * @param target 目标值
     * @return 结果
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        dfs(4, result, nums, new LinkedList<>(), target, 0, nums.length - 1);
        return result;
    }

    /**
     * 递归
     * @param n n
     * @param result 结果
     * @param nums 数组
     * @param currentCombine 当前组合
     * @param target 目标值
     * @param begin 开始索引
     * @param end 结束索引
     */
    private void dfs(int n, List<List<Integer>> result, int[] nums, LinkedList<Integer> currentCombine, int target, int begin, int end){
        if (n == 2){
            while (begin < end){
                long currSum = nums[begin] + nums[end];
                if (currSum < target){
                    begin++;
                }else if (currSum > target){
                    end--;
                }else {
                    currentCombine.push(nums[begin]);
                    currentCombine.push(nums[end]);
                    result.add(new ArrayList<>(currentCombine));
                    currentCombine.pop();
                    currentCombine.pop();
                    begin++;
                    end--;
                    while (begin < end && nums[begin] == nums[begin - 1]){
                        begin++;
                    }
                    while (begin < end && nums[end] == nums[end + 1]){
                        end--;
                    }
                }
            }
        }
        for (int k = begin; k <= end - n + 1; k++){
            if (k > begin && nums[k] == nums[k - 1]) continue;
            currentCombine.push(nums[k]);
            dfs(n - 1, result, nums, currentCombine, target - nums[k], k + 1, end);
            currentCombine.pop();
        }
    }
}
